#leetcode题目40：组数总和2
#难度：中等
#时间复杂度：O(n^2)
#空间复杂度：O(1)
#方法：回溯

from typing import List
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        
        if not candidates:
            return []

        candidates.sort()

        def dfs(index,candidates,path,res,target):
            if target==0:
                res.append(path[:])
                return
            if target<0:
                return
            for i in range(index,len(candidates)):
                if i>index and candidates[i]==candidates[i-1]:
                    continue
                path.append(candidates[i])
                dfs(index+1,candidates,path,res,target-candidates[i])
                path.pop()

        res=[]
        dfs(0,candidates,[],res,target)
        return res

#测试数据
candidates=[10,1,2,7,6,1,5]         
target=8
#预期输出：[[1,1,6],[1,2,5],[1,7],[2,6]]
solution=Solution()
print(solution.combinationSum2(candidates,target))

candidates=[2,5,2,1,2]
target=5
#预期输出：[[1,2,2],[5]]
solution=Solution()
print(solution.combinationSum2(candidates,target))


